#include "CQuadTree.h"

//--------------------------------------------------------------//
//																//
//						CQuadTree CLASS							//
//																//
//--------------------------------------------------------------//
CQuadTree::CQuadTree(ULONG maxLevel, long width, long height)
{
	m_nMaxLevel		= maxLevel;
	m_nWidth		= width;
	m_nHeight		= height;

	m_pRootNode		= new CQuadTreeNode( NULL , 0 , 0 , width , height );
}

CQuadTree::~CQuadTree()
{
	
}



//----------------------------------------------//
// Name : AddObject								//
// Desc : Add the object to the reference Node	//
//----------------------------------------------//
HRESULT CQuadTree::AddObject(CObject *object , CQuadTreeNode* pNode /*= NULL*/)
{
	if(!pNode)
		pNode = m_pRootNode;

	ULONG i = 0 , collisionIndex = 0 ;
	int index[2] = { -1 , -1 };
	RECT nodeRect[4];
	long nodeLeftX		= pNode->GetPosX();
	long nodeLeftY		= pNode->GetPosY();
	long nodeWidth		= pNode->GetWidth() / 2;
	long nodeHeight		= pNode->GetHeight() / 2;

	nodeRect[0] = CreateVirtualNode( nodeLeftX , nodeLeftY , nodeWidth , nodeHeight );
	nodeRect[1] = CreateVirtualNode( nodeLeftX + nodeWidth , nodeLeftY , nodeWidth , nodeHeight );
	nodeRect[2] = CreateVirtualNode( nodeLeftX , nodeLeftY + nodeHeight , nodeWidth , nodeHeight );
	nodeRect[3] = CreateVirtualNode( nodeLeftX + nodeWidth , nodeLeftY + nodeHeight , nodeWidth , nodeHeight );

	for ( i = 0 ; i < 4 ; ++i )
	{
		if(isCollision( object->GetBoundBox() , nodeRect[i] ) )
		{
			index[collisionIndex++] = i;
			if( collisionIndex > 1 )
				break;
		}
	}

	if( collisionIndex > 1 )
	{
		pNode->AddObject(object);
	}
	else
	{
		if( SubDivide(pNode) == S_OK )
			AddObject( object , pNode->m_pSubNode[index[0]] );
		else
			pNode->AddObject( object );
	}
	
	return S_OK;
}


//--------------------------------------------------//
// Name : SubDivide									//
// Desc : Divide the input node into 4 child node	//
//--------------------------------------------------//
HRESULT CQuadTree::SubDivide(CQuadTreeNode *pNode)
{
	if( pNode->GetLevel() < m_nMaxLevel )
	{
		if(!pNode->m_pSubNode)
		{
			long nodeLeftX		= pNode->GetPosX();
			long nodeLeftY		= pNode->GetPosY();
			long nodeWidth		= pNode->GetWidth() / 2;
			long nodeHeight		= pNode->GetHeight() / 2;
			
			pNode->m_pSubNode = new CQuadTreeNode*[4];

			pNode->m_pSubNode[0]	= new CQuadTreeNode( pNode , nodeLeftX , nodeLeftY , nodeWidth , nodeHeight );
			pNode->m_pSubNode[1]	= new CQuadTreeNode( pNode , nodeLeftX + nodeWidth , nodeLeftY , nodeWidth , nodeHeight );
			pNode->m_pSubNode[2]	= new CQuadTreeNode( pNode , nodeLeftX , nodeLeftY + nodeHeight , nodeWidth , nodeHeight );
			pNode->m_pSubNode[3]	= new CQuadTreeNode( pNode , nodeLeftX + nodeWidth , nodeLeftY + nodeHeight , nodeWidth , nodeHeight );

			return S_OK;
		}
		else
			return S_OK;
	}

	return D3DERR_INVALIDCALL;
}


//----------------------------------------------------------------------//
// Name : GetObject														//
// Desc : Get all object of all nodes that input rect collision with	//
//----------------------------------------------------------------------//
HRESULT CQuadTree::GetObject(RECT rect, std::vector<CObject*> &listObject , CQuadTreeNode* pNode /*= NULL*/)
{
	if(!pNode)
		pNode = m_pRootNode;

	if(!pNode->m_pSubNode)
	{
		pNode->GetObject(listObject);
	}
	else
	{
		pNode->GetObject(listObject);
		int index[4] = { -1 , -1 , -1 , -1 };
		ULONG i, collisionIndex = 0;

		for( i = 0 ; i < 4 ; ++i)
		{
			if(isCollision( rect , pNode->m_pSubNode[i]->GetSize() ) )
			{
				index[collisionIndex++] = i;
			}
		}

		for( i = 0 ; i < collisionIndex ; ++i)
		{
			GetObject( rect , listObject , pNode->m_pSubNode[index[i]] );
		}
	}

	return S_OK;
}



//----------------------------------------------------------//
// Name : RemoveObject										//
// Desc : Remove the input object out of the reference node	//
//----------------------------------------------------------//
HRESULT CQuadTree::RemoveObject(CObject *object , CQuadTreeNode* pNode /*= NULL*/)
{
	if( !pNode )
		pNode = m_pRootNode;

	if( pNode->RemoveObject(object) == S_OK )
		return S_OK;

	if( !pNode->m_pSubNode )
	{
		return S_OK;
	}
	else
	{
		int index[4] = { -1 , -1 , -1 , -1 };
		ULONG i, collisionIndex = 0;

		for( i = 0 ; i < 4 ; ++i)
		{
			if(isCollision( object->GetBoundBox() , pNode->m_pSubNode[i]->GetSize() ) )
			{
				index[collisionIndex++] = i;
			}
		}
		
		for( i = 0 ; i < collisionIndex ; ++i)
		{
			RemoveObject( object , pNode->m_pSubNode[index[i]] );
		}
	}

	return S_OK;
}


//------------------------------//
// Name : UpdateQuadTree		//
// Desc : Update quad tree node	//
//------------------------------//
void CQuadTree::UpdateNode(CObject *object)
{
	RemoveObject( object );
	AddObject ( object );
}




//--------------------------------------------------//
// Name : isCollision								//
// Desc : Collision detect between object and node	//
//--------------------------------------------------//
bool CQuadTree::isCollision(RECT objRect, RECT nodeRect)
{
	if ( objRect.top < nodeRect.bottom && objRect.bottom > nodeRect.top 
		&& objRect.left < nodeRect.right && objRect.right > nodeRect.left )
		return true;

	return false;
}

//----------------------------------------------------------------------------------------------------------//
// Name : CreateVirtualNode																					//
// Desc : Create virtual node for collision checking to check whether the object belong to that node or not	//
//----------------------------------------------------------------------------------------------------------//
RECT CQuadTree::CreateVirtualNode(long upperLeftX, long upperLeftY, long width, long height)
{
	RECT r;

	r.left		= upperLeftX;
	r.right		= r.left + width;
	r.top		= upperLeftY;
	r.bottom	= r.top + height;

	return r;
}


//--------------------------------------------------------------//
//																//
//					CQuadTreeNode CLASS							//
//																//
//--------------------------------------------------------------//
CQuadTreeNode::CQuadTreeNode(CQuadTreeNode* pParentNode , long upperLeftX, long upperLeftY, long width, long height)
{
	m_nUpperLeftX		= upperLeftX;
	m_nUpperLeftY		= upperLeftY;
	m_nWidth			= width;
	m_nHeight			= height;

	if(pParentNode)
	{
		m_nNodeLevel	= pParentNode->GetLevel() + 1 ;
		m_pParentNode	= pParentNode;
	}
	else
	{
		m_nNodeLevel	= 1;
		m_pParentNode	= NULL;
	}

	m_pSubNode			= NULL;
}

CQuadTreeNode::~CQuadTreeNode()
{

}




//----------------------------------//
// Name : AddObject					//
// Desc : Add object to this node	//
//----------------------------------//
void CQuadTreeNode::AddObject( CObject* object )
{
	m_listObject.push_back(object);
}


//------------------------------------------//
// Name : RemoveObject						//
// Desc : Remove an object out of this node	//
//------------------------------------------//
HRESULT CQuadTreeNode::RemoveObject(CObject* object)
{
	int size = m_listObject.size();

	if( size == 0 )
		return D3DERR_INVALIDCALL;

	for( ULONG i = 0 ; i < size ; ++i )
	{
		if( m_listObject[i] == object )
		{
			m_listObject.erase( m_listObject.begin() + i );
			return S_OK;
		}
	}

	return D3DERR_INVALIDCALL;
}


//--------------------------------------//
// Name : SetLevel						//
// Desc : Set the level for this node	//
//--------------------------------------//
void CQuadTreeNode::SetLevel(ULONG lev )
{
	m_nNodeLevel = lev;
}


//--------------------------------------//
// Name : GetLevel						//
// Desc : Get the level of this node	//
//--------------------------------------//
ULONG CQuadTreeNode::GetLevel()
{
	return m_nNodeLevel;
}


//----------------------------------------------//
// Name : GetObject								//
// Desc : Get all object belong to this node	//
//----------------------------------------------//
HRESULT CQuadTreeNode::GetObject(std::vector<CObject*> &listObject)
{
	ULONG size = m_listObject.size();
	if( size == 0 )
		return D3DERR_INVALIDCALL;

	for ( ULONG i = 0 ; i < size ; ++i)
	{
		listObject.push_back( m_listObject[i] );
	}
	return S_OK;
}




//------------------------------------------//
// Name : GetSize							//
// Desc : Get the current size of this Node	//
//------------------------------------------//
RECT	CQuadTreeNode::GetSize()
{
	RECT r;

	r.left		= m_nUpperLeftX;
	r.right		= r.left + m_nWidth;
	r.top		= m_nUpperLeftY;
	r.bottom	= r.top + m_nHeight;

	return r;
}



//----------------------------------//
// Name : GetWidth					//
// Desc : Get width of this node	//
//----------------------------------//
long CQuadTreeNode::GetWidth()
{
	return m_nWidth;
}


//----------------------------------//
// Name : GetHeight					//
// Desc : Get height of this node	//
//----------------------------------//
long CQuadTreeNode::GetHeight()
{
	return m_nHeight;
}



//------------------------------------------//
// Name : GetPosX							//
// Desc : Get the upper left X of this node	//
//------------------------------------------//
long CQuadTreeNode::GetPosX()
{
	return m_nUpperLeftX;
}

//------------------------------------------//
// Name : GetPosY							//
// Desc : Get the upper left Y of this node	//
//------------------------------------------//
long CQuadTreeNode::GetPosY()
{
	return m_nUpperLeftY;
}


















/*
CQuadTreeNode::CQuadTreeNode(long upperLeftX, long upperLeftY, long width, long height)
{
	m_UpperLeftX	=	upperLeftX;
	m_UpperLeftY	=	upperLeftY;
	m_Width			=	width;
	m_Height		=	height;

	m_ppSubNode		=	NULL;	
}


CQuadTreeNode::~CQuadTreeNode()
{
	
}

//-------------------------------------------------------//
// Name : SubDivine                                      //
// Desc : Use to divine a leaf node into 4 quadrant ,    //
//        if branch node , this method will              //
//		  divine each child node into 4 smaller quadrant //	
//-------------------------------------------------------//
HRESULT CQuadTreeNode::SubDivine()
{
	HRESULT hr = S_OK;
	int		i;

	if(!m_ppSubNode) //if has no sub node , this is a leaf we can divine it into 4 quadrant
	{
		long width	= m_Width  / 2;
		long height	= m_Height / 2;

		long ulx	= m_UpperLeftX;
		long uly	= m_UpperLeftY;

		m_ppSubNode = new CQuadTreeNode*[4];

		m_ppSubNode[0]	= new CQuadTreeNode( ulx , uly ,  width , height );					//Upper Left quadrant
		m_ppSubNode[1]	= new CQuadTreeNode( ulx + width , uly , width , height );			//Upper Right quadrant
		m_ppSubNode[2]	= new CQuadTreeNode( ulx , uly + height , width , height );			//Lower Left quadrant
		m_ppSubNode[3]	= new CQuadTreeNode( ulx + width , uly + height , width , height ); //Lower Right quadrant
	}
	else	//If has sub node , this is a branch , we check for 4 sub node and divine them into 4 smaller quadrant
	{
		for( i = 0 ; i < 4 && SUCCEEDED(hr) ; ++i)
		{
			hr = m_ppSubNode[i]->SubDivine();
		}
	}
	
	return hr;
}

//------------------------------------------------//
// Name : AddObject								  //
// Desc : Add an object to our node list ,        //
//			an object can be in multiple quadrant //
//------------------------------------------------//
HRESULT CQuadTreeNode::AddObject(IColliableObject *object)
{
	HRESULT hr = S_OK;
	ULONG	i;

	if( !m_ppSubNode )
	{
		int size = m_ListObject.size();
		for( i = 0 ; i < size ; ++i)
		{
			if(m_ListObject[i] == object)
				return D3DERR_INVALIDCALL;
		}

		m_ListObject.push_back(object);
	}
	else
	{
		ULONG collisionArray[4] = {-1 , -1 , -1 , -1 };
		ULONG collisionIndex	= 0;
		RECT rectBoundBox;
		
		long ulx	= 0;
		long uly	= 0;
		long w		= 0;
		long h		= 0;
		rectBoundBox = object->GetBoundBox( );
		
		long leftNode	=	0;
		long rightNode	=	0;
		long topNode	=	0;
		long botNode	=	0;
		for( i = 0 ; i < 4 ; ++i )
		{
			m_ppSubNode[i]->GetSize( &ulx , &uly , &w , &h );

			leftNode	=	ulx;
			rightNode	=	ulx + w;
			topNode		=	uly;
			botNode		=	uly + h;

			if( topNode < rectBoundBox.bottom || botNode > rectBoundBox.top || leftNode > rectBoundBox.right || rightNode < rectBoundBox.left )
				continue;
			else
			{
				collisionArray[collisionIndex++] = i;
			}
		}

		for( i = 0 ; i < collisionIndex ; ++i )
		{
			m_ppSubNode[collisionArray[i]]->AddObject(object);
		}
	}

	return hr;
}

//----------------------------------------------------------------//
// Name : GetObject                                               //
// Desc : Get all object in a node that our object collision with //
//----------------------------------------------------------------//
HRESULT CQuadTreeNode::GetObject(IColliableObject *object , std::vector<IColliableObject*> &listObject)
{
	HRESULT		hr = S_OK;
	ULONG		i  = 0;

	if(!m_ppSubNode)
	{
		int size = m_ListObject.size();

		for( i = 0 ; i < size ; ++i)
		{	
			listObject.push_back(m_ListObject[i]);
		}
	}
	else
	{
		ULONG collisionArray[4]	= { -1 , -1 , -1 , -1 };
		ULONG collisionIndex	= 0;
		RECT rectBoundBox;
		rectBoundBox = object->GetBoundBox( );

		long topNode	= 0;
		long botNode	= 0;
		long leftNode	= 0;
		long rightNode	= 0;

		long ulx		= 0;
		long uly		= 0;
		long w			= 0;
		long h			= 0;
		for( i = 0 ; i < 4 ; ++i)
		{
			m_ppSubNode[i]->GetSize( &ulx , &uly , &w , &h );

			leftNode	= ulx;
			rightNode	= ulx + w;
			topNode		= uly;
			botNode		= uly + h;
			
			if( topNode < rectBoundBox.bottom || botNode > rectBoundBox.top || leftNode > rectBoundBox.right || rightNode < rectBoundBox.left )
				continue;
			else
			{
				collisionArray[collisionIndex++] = i;
			}
		}

		for( i = 0 ; i < collisionIndex ; ++i)
		{
			m_ppSubNode[collisionArray[i]]->GetObject( object , listObject );
		}
	}

	return hr;
}


//-------------------------//
// Name : RemoveObject     //
// Desc : Remove an object //
//-------------------------//
HRESULT CQuadTreeNode::RemoveObject(IColliableObject *object)
{
	HRESULT hr	= S_OK;
	ULONG	i	= 0;

	if( !m_ppSubNode )
	{
		int size = m_ListObject.size();
		for( i = 0 ; i < size ; ++i)
		{
			if(m_ListObject[i] == object)
				m_ListObject.erase(m_ListObject.begin() + i);
		}
	}
	else
	{
		ULONG collisionArray[4]	= { -1 , -1 , -1 , -1 };
		ULONG collisionIndex	= 0;
		RECT rectBoundBox;
		rectBoundBox = object->GetBoundBox( );

		long topNode	= 0;
		long botNode	= 0;
		long leftNode	= 0;
		long rightNode	= 0;

		long ulx		= 0;
		long uly		= 0;
		long w			= 0;
		long h			= 0;
		for( i = 0 ; i < 4 ; ++i)
		{
			m_ppSubNode[i]->GetSize( &ulx , &uly , &w , &h );

			leftNode	= ulx;
			rightNode	= ulx + w;
			topNode		= uly;
			botNode		= uly + h;
			
			if( topNode < rectBoundBox.bottom || botNode > rectBoundBox.top || leftNode > rectBoundBox.right || rightNode < rectBoundBox.left )
				continue;
			else
			{
				collisionArray[collisionIndex++] = i;
			}
		}

		for( i = 0 ; i < collisionIndex ; ++i)
		{
			m_ppSubNode[collisionArray[i]]->RemoveObject(object);
		}
	}

	return hr;
}


//----------------------------------------------------------//
// Name : Update                                            //
// Desc : Update the node base on the position of an object //
//----------------------------------------------------------//
void CQuadTreeNode::Update(IColliableObject *Object)
{
	ULONG i = 0;

	if(!m_ppSubNode)
	{
		return;
	}
	else
	{
		for( i = 0 ; i < 4 ; ++i)
		{
			m_ppSubNode[i]->RemoveObject(Object);
		}
		for( i = 0 ; i < 4 ; ++i)
		{
			m_ppSubNode[i]->AddObject(Object);
		}
	}
}


//-------------------------//
// Name : GetSize          //
// Desc : Get size of node //
//-------------------------//
void CQuadTreeNode::GetSize(long *upperLeftX, long *upperLeftY, long *width, long *height)
{
	*upperLeftX	= m_UpperLeftX;
	*upperLeftY	= m_UpperLeftY;
	*width		= m_Width;
	*height		= m_Height;
}

*/
